/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class RP {

	/*
	RP 守恒定律

	话说天下的 RP 是守恒的，你的 RP 高了，我的 RP 可能就低了，你今天 RP 高了，明天 RP 可能就低了。我们的 RP 总是在高高低低中不断变化。有些事情做了是可以 涨 RP 的，有的事情做了是要降RP的。

	Wujitu 在发现了这个道理后，决定在期末考试前多多积累人品。他发现，他做的每件事情对 RP 有如下影响：

	  1）他做的第一件事情是涨 RP 的；
	  2）如果他做的上一件事情是涨 RP 的，那么他做的下一件事情是降 RP 的；
	  3）如果他做的上一件事情是降 RP 的，那么他做的下一件事情是涨 RP 的。

	Wujitu 现在积攒的人品是 0。涨 RP 记为 RP 值增加，降 RP 记为 RP 值减少。Wujitu 在期末考试前有 N 件事情可以做，每件事情都有自己的 RP 系数。对于这些事情，Wujitu 只可以有两种选择：做或者不做。事情的先后顺序是一定的，也就是说 Wujitu 只可以按照给定好的顺序选择做不做该事情。

	现在请你帮助 Wujitu 在期末考试之前，积攒到最多的 RP。

	输入

	每组数据包括两行，第一行有一个整数 N (N <= 1000000)，代表有 N 件事情；第二行有 N 个正整数，代表每件事情的 RP 值 r_i (r_i <= 1000000)

	输出

	输出结果仅包含一个整数，即 Wujitu 在期末前能积攒的最大 RP 值。

	样例输入

	1
	1
	4
	1 3 1 2

	样例输出

	1
	4
	           1   3    1    2
	i          0
	positive 0 0   0    2   2 
	negative 0 1   3    3   4
	temp     0 0   1    3   3
	*/
	public int maxRP(int[] actions) {
		if (actions == null || actions.length == 0)
			return 0;
		int positive = 0, negative = 0;
		for (int i = 0; i < actions.length; i++) {
			int temp = negative;
			if (positive + actions[i] > negative)
				negative = positive + actions[i];
			if (temp - actions[i] > positive)
				positive = temp - actions[i];
		}

		return Math.max(negative, positive);
	}

	/*
	 * 解题思路：
	 * 这题其实是一道动态规划题，用两个数组存放某件事做与不做的后果。最后比较数组的值即可。每一步与下一步都是相关联的。
	 */
	public int maxRP1(int[] actions) {
		if (actions == null || actions.length == 0)
			return 0;

		int number = actions.length;
		int[] f = new int[2];
		int[] g = new int[2];

		f[0] = 0;
		g[0] = 0;

		for (int i = 0; i < number; i++) {
			if (f[(i) % 2] < g[(i) % 2] + actions[i])
				f[(i + 1) % 2] = g[i % 2] + actions[i];
			else
				f[(i + 1) % 2] = f[i % 2];

			if (g[i % 2] < f[i % 2] - actions[i])
				g[(i + 1) % 2] = f[i % 2] - actions[i];
			else
				g[(i + 1) % 2] = g[i % 2];
		}

		if (g[number % 2] > f[number % 2])
			f[number % 2] = g[number % 2];

		return f[number % 2];
	}

	int max_rp(int[] actions) {
		int up = actions[0];
		int down = 0;
		for (int i = 1; i < actions.length; ++i) {
			int tmp = up;
			up = Math.max(actions[i] + down, up);
			down = Math.max(-actions[i] + tmp, down);
		}
		return up;
	}

	/**
	 * 
	 */
	public RP() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		RP rp = new RP();
		int[] actions = { 1, 3, 1 };
		System.out.println(rp.maxRP1(actions));
	}
}
